public class test2 {
    /**
     * 给定两个序列X={x1, x2,…, xm}和Y={y1,y2,…,yn}，试找出X和Y的最长公共子序列。
     * 比如，对长度为7的串X={C, B, C, B, D, A, C}，和长度为6的串Y={B, D, C, A, B, A}，它们最长公共子序列为Z={B,C,B,A}，长度为4。
     *
     * 用C/C++/Python语言伪代码描述算法流程，包括：计算最长公共子序列长度的过程，以及生成最长公共子序列的过程。用Java写的顺手
     */

    public static void main(String[] args) {
        char[] X = {'C', 'B', 'C', 'B', 'D', 'A', 'C'};
        char[] Y = {'B', 'D', 'C', 'A', 'B', 'A'};
        int m = X.length;
        int n = Y.length;
        longest_common_subsequence(X,Y,m,n);
    }

    public static void longest_common_subsequence(char[] X,char[]Y,int m,int n){
        // 初始化dp数组为[0,i]和[0，j]结尾的字符串的最长公共子序列的长度
            int[][] dp = new int[m + 1][n + 1];
            int i, j;

            // 初始化边界条件
            for (i = 0; i <= m; i++) {
                dp[i][0] = 0;
            }
            for (j = 0; j <= n; j++) {
                dp[0][j] = 0;
            }

            // 计算最长公共子序列长度的过程
            for (i = 1; i <= m; i++) {
                for (j = 1; j <= n; j++) {
                    if (X[i-1] == Y[j-1]) {
                        dp[i][j] = dp[i-1][j-1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                    }
                }
            }

            // 生成最长公共子序列的过程
            int lcs_length = dp[m][n];
            char[] lcs = new char[lcs_length];
            i = m;
            j = n;
            int k = lcs_length - 1;
            while (i > 0 && j > 0) {
                if (X[i-1] == Y[j-1]) {
                    lcs[k] = X[i-1];
                    i--;
                    j--;
                    k--;
                } else if (dp[i-1][j] > dp[i][j-1]) {
                    i--;
                } else {
                    j--;
                }
            }

            System.out.print("The longest common subsequence is: ");
            for (i = 0; i < lcs_length; i++) {
                System.out.print(lcs[i] + " ");
            }
            System.out.println();
            System.out.println("The length of the longest common subsequence is: " + lcs_length);
        }

}
